To use fabrication equipment purchased for larger technology nodes, multiple exposure or multi-patterning technology (MPT) has been developed. MPT involves forming patterns by using multiple different masks in succession. MPT is a layout splitting method analogous to a coloring problem for layout splitting in graph theory.